package com.sheng.leetcode.year2023.month01.day04;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/01/04
 * <p>
 * 1802. 有界数组中指定下标处的最大值<p>
 * <p>
 * 给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：<p>
 * nums.length == n<p>
 * nums[i] 是 正整数 ，其中 0 <= i < n<p>
 * abs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1<p>
 * nums 中所有元素之和不超过 maxSum<p>
 * nums[index] 的值被 最大化<p>
 * 返回你所构造的数组中的 nums[index] 。<p>
 * 注意：abs(x) 等于 x 的前提是 x >= 0 ；否则，abs(x) 等于 -x 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 4, index = 2,  maxSum = 6<p>
 * 输出：2<p>
 * 解释：数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 6, index = 1,  maxSum = 10<p>
 * 输出：3<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= maxSum <= 10^9<p>
 * 0 <= index < n<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array">1802. 有界数组中指定下标处的最大值</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1802 {

    @Test
    public void test01() {
//        int n = 4, index = 2, maxSum = 6;
//        int n = 6, index = 1, maxSum = 10;
//        int n = 4, index = 0, maxSum = 4;
        int n = 3, index = 0, maxSum = 815094800;
        System.out.println(new Solution().maxValue(n, index, maxSum));
    }
}

class Solution {
    public int maxValue(int n, int index, int maxSum) {
        /**
         * 要求：数组元素全部为正整数即最小值为 1 ，且相邻两个元素之间的差值小余等于 1 ，数组所有元素之和不超过 maxSum ， nums[index] 的值被最大化
         * 假设 nums[index] 的值为 x，那么他左半部分的值为 (x - 1) + (x - 2) + (x - 3) + ... + 1 + 1 + ... 递减 index 次，直至递减结束或者递减到 1 ，然后保持
         * 分两种情况讨论，一种是优化到后面全部为 1 ，一种是减不到 1
         * if (x >= left) {
         *     sum += left * x - left * (left + 1) / 2;
         * } else {
         *     sum += x * (x - 1) / 2 + left - x;
         * }
         * 二分查找进行优化
         */
        int left = 1, right = maxSum;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            // 计算左右两边之和是否超过了 maxSum
            if (sum(mid - 1, index) + sum(mid, n - index) <= maxSum) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    public long sum(long x, int cnt) {
        return x >= cnt ? (x + x - cnt + 1) * cnt / 2 : x * (x + 1) / 2 + cnt - x;
    }
}
